package 所有的题类.单调队列;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class TheMonotonePriorityQueue {
    public static void main(String[] args) {
        int a[]={1,3,-1,-3,5,3,6,7};
        Arrays.stream(maxSlidingWindow(a, 3)).forEach(System.out::println);
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list=new ArrayList();
        LinkedList<Integer> queue= new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            //如果当前下标超过则移除
            if(queue.isEmpty()){
                queue.add(i);
            }else{
                if(i-queue.getFirst()>k-1){
                    queue.poll();
                }
                while (!queue.isEmpty() && nums[queue.getLast()]<nums[i]){
                    queue.removeLast();
                }
                queue.addLast(i);
            }
            if(i>=k-1){
                list.add(nums[queue.peek()]);
            }
        }
        int [] a=new int[list.size()];
        for(int i=0;i<a.length;i++){
            a[i]=list.get(i);
        }
        return a;
    }
}
